package com.yahoo.labs.snow.solver;

import it.unimi.dsi.fastutil.ints.IntOpenHashSet;

import java.util.Vector;

import com.yahoo.labs.snow.ProblemInstance;
import com.yahoo.labs.snow.Snowflake;

/**
 * Iteratively picks pivots, builds a good snowflake around each pivot, then picks another pivot.
 * 
 * @author chato
 * 
 */
public abstract class SnowflakesOneByOneSolver extends MultiplicativeEffortProduceAndChooseSolver {

	/**
	 * True iff a node that has been already picked as part of a snowflake (by some other pivot) can
	 * be a pivot in the future.
	 */
	boolean SNOWFLAKE_MEMBERS_CAN_BE_PIVOTS = false;

	public SnowflakesOneByOneSolver(ProblemInstance problem) {
		super(problem);
	}

	abstract int getPivot(IntOpenHashSet pivotsUsed, IntOpenHashSet possiblePivots);

	@Override
	Vector<Snowflake> produceManySnowflakes(int numToProduce) {
		Vector<Snowflake> candidates = new Vector<Snowflake>();

		IntOpenHashSet pivotsUsed = new IntOpenHashSet();
		IntOpenHashSet possiblePivots = new IntOpenHashSet(problem.getIds());
		IntOpenHashSet allIds = new IntOpenHashSet(problem.getIds());

		int maxTrials = numToProduce * 1000; // Avoid getting stuck
		
		int trials = 0;
		
		while( (candidates.size() < numToProduce) && (possiblePivots.size() > 0) && ( trials < maxTrials ) ) {
			int pivot = getPivot(pivotsUsed, possiblePivots);
			if (pivotsUsed.contains(pivot) || (!possiblePivots.contains(pivot))) {
				throw new IllegalStateException("Invalid pivot");
			}

			logger.info("Pivot choosen: " + pivot);
			pivotsUsed.add(pivot);
			possiblePivots.remove(pivot);

			Snowflake snowflake = pickFlake(pivot, allIds);
			if (candidateAcceptable(snowflake)) {
				candidates.add(snowflake);

				if (!SNOWFLAKE_MEMBERS_CAN_BE_PIVOTS) {
					// Remove all snowflake members from the possible pivots
					for (int id : snowflake.ids()) {
						possiblePivots.remove(id);
					}
				}
			}
			trials++;
		}
		
		if( trials >= maxTrials ) {
			Solver.logger.warn( "Number of trials was exhausted" );
		}
		
		return candidates;
	}

	/**
	 * Indicates if a candidate is acceptable or not.
	 * 
	 * @param candidate
	 * @return true iff the candidate is acceptable.
	 */
	boolean candidateAcceptable(Snowflake candidate) {
		return true;
	}
}
